public class Main {
    /**
     * 链表相交
     * https://leetcode.cn/problems/intersection-of-two-linked-lists-lcci/
     * 给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表没有交
     * 点，返回 null 。
     */
    public static void main(String[] args) {
        System.out.println("hello world >_0");
        // 链表A
        ListNode headA = new ListNode(4);
        headA.next = new ListNode(1);
        headA.next.next = new ListNode(8);
        headA.next.next.next = new ListNode(4);
        headA.next.next.next.next = new ListNode(5);
        // 链表B
        ListNode headB = new ListNode(5);
        headB.next = new ListNode(0);
        headB.next.next = new ListNode(1);
        headB.next.next = headA.next.next;

        ListNode answer = new Main().getIntersectionNode(headA, headB);

        while (answer != null) {
            System.out.println(answer.val);
            answer = answer.next;
        }
    }

    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        int lenghthA = 0;
        int lenghthB = 0;
        ListNode cur = headA;
        while (cur != null) {
            cur = cur.next;
            lenghthA++;
        }
        cur = headB;
        while (cur != null) {
            cur = cur.next;
            lenghthB++;
        }
        int n = lenghthA > lenghthB ? lenghthA - lenghthB : lenghthB - lenghthA;

        ListNode curA = headA;
        ListNode curB = headB;
        if (lenghthA > lenghthB) {
            for (int i = n; i > 0; i--) {
                curA = curA.next;
            }
            while (curA != null && curB != null) {
                if (curA == curB) {
                    return curA;
                }
                curA = curA.next;
                curB = curB.next;
            }
        }
        else {
            for (int i = n; i > 0; i--) {
                curB = curB.next;
            }
            while (curB != null && curA != null) {
                if (curB == curA) {
                    return curB;
                }
                curA = curA.next;
                curB = curB.next;
            }
        }
        return null;
    }
}

class ListNode {
    int val;
    ListNode next;

    public ListNode() {
    }

    public ListNode(int val) {
        this.val = val;
    }
}
